package org.hot100_2;

import java.util.Deque;
import java.util.LinkedList;

public class leetcode239 {
    public int [] maxSlidingWindow(int [] nums,int k){

        int n = nums.length;
        int [] res = new int[n-k+1];

        //用来更新结果
        int index =0;
        //维护有序双端队列，队列中存放的是索引，有序指的是：索引对应的值是有序的，队列的出队元素是最大的，入队元素是最小的（在当前窗口中）
        Deque<Integer> deque = new LinkedList<>();

        int left ;
        //i为窗口的右边界
        for (int i = 0; i < n; i++) {
            //left为窗口的左边界
            left=i-k+1;

            //更新数据前，判断当前队列的最大值是否在当前窗口内
            while (!deque.isEmpty() && deque.peekFirst()<left){
                deque.removeFirst();
            }

            //确保队列中的数据是有序的
            while (!deque.isEmpty() && nums[i]>nums[deque.peekLast()]){
                deque.removeLast();
            }

            deque.offer(i);

            if (i>=k-1){
                res[index] = nums[deque.peekFirst()];
                index++;
            }
        }

        return res;
    }
}
